package com.company.gxcpc2018;

import java.util.Scanner;

public class Gxcpc5 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] init = new int[]{1, 2, 3, 4};
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            if (n < 4) {
                n = 1;
            } else {
                n -= 2;
            }
            if (n <= 4) {
                System.out.println(init[n - 1]);
                continue;
            }
            long num = 0;
            if (n % 3 == 1) {
                num = (long) Math.pow(3, (n / 3 - 1) + 0.0) * 4;
            } else {
                num = (long) Math.pow(3, n / 3 + 0.0);
                if (n % 3 != 0) {
                    num *= (n % 3);
                }
            }
            System.out.println(num);
        }
    }
}
